package matrics;

import java.io.Serializable;
import java.util.Collections;
import java.util.Set;
import java.util.Vector;

public class SparseVector implements Serializable{

	private final int N; // length
	private ST<Integer, Double> st; // the vector, represented by index-value
									// pairs
	public boolean isEmpty = true;
	// initialize the all 0s vector of length N
	public SparseVector(int N) {
		this.N = N;
		this.st = new ST<Integer, Double>();
	}

	// put st[i] = value
	public void put(Integer i, double value) {
		if (i < 0 || i >= N)
			throw new RuntimeException("Illegal index " + i + " " + N);
		if (value == 0.0)
			st.remove(i);
		else{
			st.put(i, value);
			this.isEmpty = false;
		}
	}

	// return st[i]
	public double get(Integer i) {
		if (i < 0 || i >= N)
			throw new RuntimeException("Illegal index " + i);
		if (st.contains(i))
			return st.get(i);
		else
			return 0.0;
	}

	// return the number of nonzero entries
	public int nnz() {
		return st.size();
	}

	// return the size of the vector
	public int size() {
		return N;
	}

	// return the dot product of this vector a with b
	public double dot(SparseVector b) {
		SparseVector a = this;
		if (a.N != b.N)
			throw new RuntimeException("Vector lengths disagree");
		double sum = 0.0;

		// iterate over the vector with the fewest nonzeros
		if (a.st.size() <= b.st.size()) {
			for (Integer i : a.st)
				if (b.st.contains(i))
					sum += a.get(i) * b.get(i);
		} else {
			for (Integer i : b.st)
				if (a.st.contains(i)){
					//System.out.println("SparseVector: a.get(i)"+ a.get(i)+" "+b.get(i));
					sum += a.get(i) * b.get(i);
				}
		}
		return sum;
	}

	// return the 2-norm
	public double norm() {
		SparseVector a = this;
		return Math.sqrt(a.dot(a));
	}

	// return alpha * a
	public SparseVector scale(double alpha) {
		SparseVector a = this;
		SparseVector c = new SparseVector(N);
		for (Integer i : a.st)
			c.put(i, alpha * a.get(i));
		return c;
	}

	// return a + b
	public SparseVector plus(SparseVector b) {
		SparseVector a = this;
		if (a.N != b.N)
			throw new RuntimeException("Vector lengths disagree");
		SparseVector c = new SparseVector(N);
		for (Integer i : a.st)
			c.put(i, a.get(i)); // c = a
		for (Integer i : b.st)
			c.put(i, b.get(i) + c.get(i)); // c = c + b
		return c;
	}

	// return a string representation
	public String toString() {
		String s = "";
		for (Integer i : st) {
			s += "(" + i + ", " + st.get(i) + ") ";
		}
		return s;
	}

	public Vector<Integer> getOrderedKeyVector() {
		Set<Integer> k = this.st.keyset();
		Vector v = new Vector<Integer>(k);
		Collections.sort(v);
		return v;
	}

}
